/* 

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

示例：
输入: nums = [1,2,3,1], k = 3
输出: true

*/

/* 
思路：哈希表
*/

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
 var containsDuplicate = function(nums,k) {
    // 思路
    /* let map = new Map()
    for (let i = 0; i < nums.length; i++) {
        // 增加判断两个索引的绝对值是否超过k
        if(map.has(nums[i])&&Math.abs(map.get(nums[i])-i)<=k){
            return true
        }else{
            map.set(nums[i],i)
        }
    }
    return false */

    // 优化：每超过k的时候将之前存储的属性删除(减少空间复杂度)
    let map = new Map()
    for (let i = 0; i < nums.length; i++) {
        if(map.has(nums[i])){
            return true
        }
        map.set(nums[i],i)
        // 如果存储的元素超过了k，移除掉前面与此时i相隔k的项
        if(map.size>k){
            map.delete(nums[i-k])
        }
    }
    return false
};

/* 

*/

// 运行
let nums = [1,2,3,1]
let res = containsDuplicate(nums,3)
console.log(res);